package _17_剑指Offer;

public class _53_剑指Offer在排序数组中查找数字I {

    public static void main(String[] args) {

        _53_剑指Offer在排序数组中查找数字I v = new _53_剑指Offer在排序数组中查找数字I();

        int[] ins = new int[]{5, 7, 7, 8, 8, 10};
        System.out.println(v.search(ins, 7));

    }


    // 首先使用二分法，查找元素位置
    public int search(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int begin = 0;
        int end = nums.length - 1;
        // 找到第一个大于等于其的数字
        int result = end;
        while (begin <= end) {
            int mid = begin - ((begin - end) >> 1);
            if (nums[mid] >= target) {
                result = mid;
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }

        // 统计数字
        int count = 0;
        for (int i = result; i < nums.length; i++) {
            if (nums[i] != target) {
                break;
            }
            count++;
        }
        return count;
    }

}
